﻿#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#define ll __int64
#define K 1000000000

int pd(int f[], int p)
{
    int i;
    for (i = 0; i < 44; i++)
    {
        if (f[i] == p)
            return 1;
    }
    return 0;
}

int main()
{
    int i, j;
    int f[56];
    f[0] = 1;
    f[1] = 2;
    for (i = 1; i < 44; i++)
    {
        f[i + 1] = f[i] + f[i - 1];
    }
    //printf("%d",f[43]);
    int T;
    scanf("%d", &T);
    while (T--)
    {
        int n;
        scanf("%d", &n);
        int count = 0;
        for (i = 0; f[i] < n; i++)
        {
            for (j = i; f[i] + f[j] < n; j++)
            {
                int p = n - f[i] - f[j];
                if (pd(f, p) == 1 && p >= f[j])
                {
                    count++;
                    //printf("%d%d%d\n",f[i],f[j],p);
                }
            }
        }
        printf("%d\n", count);


    }
    return 0;
}


/*
题目描述
小明非常喜欢Fibonacci数列，数列为 f1=1,f2=2,fn=fn−1+fn−2。 小明想知道对于一个整数n，使得n=fi+fj+fk的组合有多少种？ 比如5=1+1+3 或者 5=1+2+2,有2种。注意 1+2+2 和 2+1+2 被认为是同一种。

输入
第一行是一个整数T(1≤T≤1000)，表示样例的个数。

每个样例是一个整数n(3≤n≤109)。

输出
依次每行输出一个样例的结果，为一个整数。

样例输入
2
3
5
样例输出
1
2
*/